The present invention relates to cryptographic method and apparatus for enciphering messages of a computer or the like.
Currently, many enterprises have been reinforcing their information network facilities for the purpose of their businesses. It is anticipated, that, in the near future, information exchanges are going to be carried out frequently among a plurality of organizations having a variety of transaction relationships with each other, not being restricted to only within one organization. Under such circumstances, ciphers are indispensable in order to assure securities of communications.
Ciphers are broadly classified into two types, that is, common key ciphers and public key ciphers. Common key cipher is used to encipher or decipher a large volume of data and to generate message authentication codes.
Public key cipher is used to secretly distribute common keys between communicating parties and to make digital signatures. Common key cipher is used to encipher and decipher messages between a message transmitter and a receiver such that the transmitter transforms a message by using a common key and transmits a ciphertext and that the receiver of the ciphertext deciphers the ciphertext to transform the ciphertext into the original message by using the same common key, under the assumption that the transmitter and the receiver share the same key (common key).
As conventional typical encipher algorithms, the DES algorithm (Data Encryption Standard) and the FEAL algorithm (Fast Encipherment Algorithm) have been known. The DES algorithm has been described in detail, for instance, (1) Koyama et al., "Modern Theory of Encryption", The Institute of Electronics and Communication Engineers of Japan, pages 41 to 49, September 1986. On the other hand, the FEAL algorithm has been described in detail in, (2) Shimizu et al., "Fast Data Encipherment Algorithm FEAL", Papers of the Institute of Electronics and Communication Engineers of Japan, D. Vol. J70-D, No. 7, pages 1413 to 1423, July 1987.
As approaches for improving the efficiency of both data scrambling (data ramdomizing) and processing speed, there have been known "Multi-Media Encryption Algorithm" (Information Processing Society of Japan, Study Group of Multi-Media Communication and Decentralized Processing, Jan. 19, 1989) and an encryption algorithm (hereinafter to be referred to as MULTI 2) disclosed in U.S. Pat. No. 4,982,429 by the inventors of the present invention.
MULTI 2 is operated to obtain 64 bits of a ciphertext by executing operations of basic functions (involution functions) .pi..sub.1 to .pi..sub.4 to a plaintext of 64-bit length including upper 32 bits and lower 32 bits, in a predetermined sequence, as shown in FIG. 14.
In FIG. 14, .sym. denotes an exclusive logical OR for each bit, + an addition using 2.sup.32 as a modulus, .sup.ROT n a cyclic shift of n bits, a V a logical OR for each bit.
It is known, that, in general, there is a risk that encipher keys used in a statement are vulnerable to be conjected and ciphertexts are deciphered illegally as a result, by a method of analyzing plaintexts which have been given to an encryption algorithm and a ciphertext which has been generated by using the plaintexts (a so-called chosen plaintext attack), even if the encryption algorithm is considered to have a considerable degree of randomness (refer to Boer, "Crypta-analysis of F.E.A.L.", Proc. EUROCRYPTO, 1987).
Therefore, the above-described conventional algorithm cannot necessarily continue to be safe in future.
In order to prevent a chosen plaintext attack, it is effective to use both an applicational countermeasure, such as reducing the cycle of altering encipher keys and a technical countermeasure, such as further complicating the encryption algorithm itself, to thereby avoid an attack of decipherment. As the latter technical countermeasure, increasing the frequency of involution transformation has been proposed in the DES, EFEL-8 and MULTI 2 (Takaragi, et al., "Development of Multi-Media Encryption Algorithm HISECURITY MULTI 2 and Its Operation Mode", The Institute of Electronics and Communication Engineers of Japan", WCIs' 89-D2, Aug. 28-30, 1989 and H. J. Highland, "Cracking the DES ?", Computers & Security, 8, 1989, pp. 274-275).
No optimum number of repetition of involutions, however, has ever been known. In other words, either a level of number of repetitions above which ciphertexts are safe or a level of number of repetition below which ciphertexts are vulnerable to a decipher attack has never been known. Accordingly, there has been no alternative method except that number of repetitions of involutions is increased to an excessive level by taking into account a safety margin. On the other hand, an increase in the number of repetitions of involutions has a problem that a speed of transforming ciphers becomes slower in inverse proportion to the increase in the number of repetitions.